package com.arjun.sort;

public class QuickSort {
	int[] A;
	int order;
    
    private int median(int l,int h){
            int mid = l+(h-l)/2;
            if(A[mid]>=A[h]){
                    if(A[mid]<=A[l])
                            return A[mid];
                    else if(A[h]>A[l])
                            return A[h];
            }
            else
            {
                    if(A[mid]>=A[l])
                            return A[mid];
                    else if(A[l]>A[h])
                            return A[h];
            }
            return A[l];
    }
    private Point partition(int l, int h){
            Point P = new Point();
            int low=l;
            int mid=l;
            int high=h;
            int pV=median(l,h);
            while(mid<=high){
                    if(A[mid]==pV)
                            mid++;
                    else if(order*A[mid]<order*pV){
                            swap(low,mid);
                            low++;mid++;
                    }
                    else{
                            swap(high,mid);
                            high--;
                    }
            }
            P.setLow(low-1);
            P.setHigh(high+1);
            return P;
    }
   
    private void swap(int i, int j){
            int temp=A[i];
            A[i]=A[j];
            A[j]=temp;
    }
   
    public void quickSortHelper(int[] a,String... orderr){
            A=a;
            if(orderr[0].equals("descend"))
            	order=-1;
            else
            	order=1;
            quickSort(0,A.length-1);
    }
   
    private void quickSort(int low, int high){
            if(low>high)
                    return;
            Point p= partition(low,high);
            quickSort(low,p.getLow());
            quickSort(p.getHigh(),high);
    }
    public void printArray(){
    	System.out.println();
            for(int i=0;i<A.length;i++)
                    System.out.print(A[i]+ " ");
            
    }
}
